package leetcode.code1914;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

//	[[3970,1906,3608,298,3072,3546,1502,773,4388,3115,747,3937],[2822,304,4179,1780,1709,1058,3645,681,2910,2513,4357,1038],[4471,2443,218,550,2766,4780,1997,1672,4095,161,4645,3838],[2035,2350,3653,4127,3208,4717,4347,3452,1601,3725,3060,2270],[188,2278,81,3454,3204,1897,2862,4381,3704,2587,743,3832],[996,4499,66,2742,1761,1189,608,509,2344,3271,3076,108],[3274,2042,2157,3226,2938,3766,2610,4510,219,1276,3712,4143],[744,234,2159,4478,4161,4549,4214,4272,701,4376,3110,4896],[4431,1011,757,2690,83,3546,946,1122,2216,3944,2715,2842],[898,4087,703,4153,3297,2968,3268,4717,1922,2527,3139,1516],[1086,1090,302,1273,2292,234,3268,2284,4203,3838,2227,3651],[2055,4406,2278,3351,3217,2506,4525,233,3829,63,4470,3170],[3797,3276,1755,1727,1131,4108,3633,1835,1345,1293,2778,2805],[1215,84,282,2721,2360,2321,1435,2617,1202,2876,3420,3034]]
//	405548684
	public int[][] rotateGrid(int[][] grid, int k) {
//		H.printObject(grid);
		int m = grid.length, n = grid[0].length;
		// 最大转移步数
		int min = Math.min(m, n);
		int min2 = min >> 1;
		int max = Math.max(m, n);// 最多走max - 1 步
		// dpMove2[x][y] = z 含义 x位置走y步到 z
		int[][] dpMove2 = new int[m * n][max];
		// dpMoveMax[x] = y 含义 x位置最多走y步不转弯
		int[] dpMoveMax = new int[m * n];
		// round[x] = y , x位置一圈长度y
		int[] girths = new int[m * n];
		int girth = (m + n - 2) << 1;
		// 起始位置[0,0],起始位置转移方向右下[1,1],填装dp方向向下[1,0],填装步数m - 1,层控制min2,待填装dp,列宽,最大步长
		fillDp(0, 0, 1, 1, 1, 0, m - 1, min2, dpMove2, n, dpMoveMax, girth, girths);
		fillDp(m - 1, 0, -1, 1, 0, 1, n - 1, min2, dpMove2, n, dpMoveMax, girth, girths);
		fillDp(m - 1, n - 1, -1, -1, -1, 0, m - 1, min2, dpMove2, n, dpMoveMax, girth, girths);
		fillDp(0, n - 1, 1, -1, 0, -1, n - 1, min2, dpMove2, n, dpMoveMax, girth, girths);
//		H.printObject(dpMoveMax);
//		H.printObject(dpMove2);
//		H.printObject(girths);
		int[][] ans = new int[m][n];
		for (int i = 0; i < m; i++) {
//			H.printObject(ans);
			for (int j = 0; j < n; j++) {
				int cur = grid[i][j];
				int index = this.index(i, j, n);
				int move = k % girths[index];
				while (move >= 0) {
					int moveMax = dpMoveMax[index];
					if (moveMax >= move) {
						int move2 = dpMove2[index][move];
						int x2 = move2 / n, y2 = move2 % n;
						ans[x2][y2] = cur;
					} else {
						index = dpMove2[index][moveMax];
					}
					move -= moveMax;
				}
			}
		}
//		H.printObject(ans);
		return ans;
	}

	private void fillDp(int startx, int starty, int startx2, int starty2, int dpx, int dpy, int step, int size,
			int[][] dp, int n, int[] dpMoveMax, int girth, int[] girths) {
		if (size == 0) {
			return;
		}
		for (int i = 0; i < step; i++) {
			int myStartx = startx + dpx * i, myStarty = starty + dpy * i;
			int index = this.index(myStartx, myStarty, n);
			int MoveMax = step - i;
			dpMoveMax[index] = MoveMax;// 最大移动范围
			girths[index] = girth;// 周长
			dp[index][0] = index;//
			for (int s = 1; s <= MoveMax; s++) {
				int index2 = this.index(myStartx + dpx * s, myStarty + dpy * s, n);
				dp[index][s] = index2;
			}
		}
		this.fillDp(startx + startx2, starty + starty2, startx2, starty2, dpx, dpy, step - 2, size - 1, dp, n,
				dpMoveMax, girth - 8, girths);//girth - 4 错大了
	}

	public int index(int i, int j, int n) {
		return i * n + j;
	}

	public void magic(int m, int n) {
		int min = Math.min(m, n);
		int max = Math.max(m, n);// 最多走max - 1 步
		// dp[x][y] = z 意味着 x位置走y步到 z
		int[][] dpMove2 = new int[m * n][max];
		int[] dpMoveMax = new int[m * n];
		int[] girths = new int[m * n];
		int girth = (m + n - 2) << 1;
		int min2 = min >> 1;
		// 起始位置[0,0],起始位置转移[1,1],填装dp方向向下[1,0],填装步数,层控制min2,待填装dp,列宽
		fillDp(0, 0, 1, 1, 1, 0, m - 1, min2, dpMove2, n, dpMoveMax, girth, girths);
		fillDp(m - 1, 0, -1, 1, 0, 1, n - 1, min2, dpMove2, n, dpMoveMax, girth, girths);
		fillDp(m - 1, n - 1, -1, -1, -1, 0, m - 1, min2, dpMove2, n, dpMoveMax, girth, girths);
		fillDp(0, n - 1, 1, -1, 0, -1, n - 1, min2, dpMove2, n, dpMoveMax, girth, girths);
	}

//	private int[] info(int m, int n, int i, int j, int k) {
//		int u = i, l = j, r = n - j - 1, d = m - i - 1;
//		int min = Math.min(Math.min(u, d), Math.min(l, r));
//		int less = min * 2;
//		int round = (m + n) * 2 - 4 - less * 4;
//		k %= round;
//		int[] size = new int[] { n - less, m - less, n - less, m - less };
//		int[] rests = new int[] {};
//		int direction = 0;// 0,1,2,3 左下右上
//		if (min == u) {
//			direction = min == l ? 1 : 0;
//		} else if (min == l) {
//			direction = min == d ? 2 : 1;
//		} else if (min == d) {
//			direction = min == r ? 3 : 2;
//		} else {
//			direction = min == u ? 0 : 3;
//		}
//		int L = min, R = n - min - 1;
//		int U = min, D = m - min - 1;
//		if (direction == 0) {
//
//		}
//		return new int[] { direction, round, less };
//	}

	@Override
	public void debug4() {
		H.compare(H.str2array1("[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]"), this.rotateGrid(H.str2array1("[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]"), 2));
//		H.compare(H.str2array1("[[188,2035,4471,2822,3970,1906,3608,298,3072,3546,1502,773],[996,1058,3645,681,2910,2513,4357,4645,3060,743,3076,4388],[3274,1709,4376,3944,2527,3838,63,3829,233,4525,3712,3115],[744,1780,1276,4478,3226,2742,3454,4127,3208,2506,3110,747],[4431,4179,3271,2690,83,4161,2938,1761,4717,3217,2715,3937],[898,304,2587,4153,3297,946,3546,3204,4347,3351,3139,1038],[1086,2443,3725,1273,2968,4214,4549,1897,3452,2278,2227,3838],[2055,2350,161,2292,3268,2610,3766,2862,1601,302,4470,2270],[3797,2278,4095,234,4717,608,1189,4381,3704,703,2778,3832],[1215,4499,1672,3268,1122,4272,4510,509,2344,757,1293,108],[84,2042,1997,2284,4203,1922,2216,701,219,2159,1345,4143],[282,234,4780,2766,550,218,3653,81,66,2157,1835,4896],[2721,1011,4087,1090,4406,3276,1755,1727,1131,4108,3633,2842],[2360,2321,1435,2617,1202,2876,3420,3034,2805,3170,3651,1516]]"),this.rotateGrid(H.str2array1("[[3970,1906,3608,298,3072,3546,1502,773,4388,3115,747,3937],[2822,304,4179,1780,1709,1058,3645,681,2910,2513,4357,1038],[4471,2443,218,550,2766,4780,1997,1672,4095,161,4645,3838],[2035,2350,3653,4127,3208,4717,4347,3452,1601,3725,3060,2270],[188,2278,81,3454,3204,1897,2862,4381,3704,2587,743,3832],[996,4499,66,2742,1761,1189,608,509,2344,3271,3076,108],[3274,2042,2157,3226,2938,3766,2610,4510,219,1276,3712,4143],[744,234,2159,4478,4161,4549,4214,4272,701,4376,3110,4896],[4431,1011,757,2690,83,3546,946,1122,2216,3944,2715,2842],[898,4087,703,4153,3297,2968,3268,4717,1922,2527,3139,1516],[1086,1090,302,1273,2292,234,3268,2284,4203,3838,2227,3651],[2055,4406,2278,3351,3217,2506,4525,233,3829,63,4470,3170],[3797,3276,1755,1727,1131,4108,3633,1835,1345,1293,2778,2805],[1215,84,282,2721,2360,2321,1435,2617,1202,2876,3420,3034]]"), 405548684));
//		H.compare(H.str2array1("[[10,20],[40,30]]"), this.rotateGrid(H.str2array1("[[40,10],[30,20]]"), 1));
//		H.compare(H.str2array1("[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]"),
//				this.rotateGrid(H.str2array1("[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]"), 2));
//		this.rotateGrid(H.str2array1("[[40,10],[30,20]]"), 1);
//		[[36,1,2,3,4,5],[6,7,8,9,10,11],[12,13,14,15,16,17],[18,19,20,21,22,23],[24,25,26,27,28,29],[30,31,32,33,34,35]]
//				100
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
